/*
 * 0096. 链表划分
 * 给定一个单链表和数值x，划分链表使得所有小于x的节点排在大于等于x的节点之前。
 * 你应该保留两部分内链表节点原有的相对顺序。
 * https://www.lintcode.com/problem/partition-list/description
 * 
 * 样例
 * 给定链表 1->4->3->2->5->2->null，并且 x=3
 * 返回 1->2->2->4->3->5->null
 * 
 * 2018.07.14 @jeyming
 */
package partition_list_0096;

// Definition for ListNode
class ListNode {
	int val;
	ListNode next;
	ListNode(int x) {
		val = x;
		next = null;
	}
}

public class Partition_list_0096 {
	/**
	 * @param head: The first node of linked list
	 * @param x: An integer
	 * @return: A ListNode
	 */
	public ListNode partition(ListNode head, int x) {
		// write your code here
		if(head == null) {
			return null;
		}
		ListNode p = head;
		ListNode resA = null, pA = null;
		ListNode resB = null, pB = null;
		boolean judgeA = true;
		boolean judgeB = true;
		while(p != null) {
			if(p.val < x) {
				if(judgeA) {
					resA = new ListNode(p.val);
					pA = resA;
					judgeA = false;
				} else {
					pA.next = p;
					pA = pA.next;
				}
			} else {
				if(judgeB) {
					resB = new ListNode(p.val);
					pB = resB;
					judgeB = false;
				} else {
					pB.next = p;
					pB = pB.next;
				}
			}
			p = p.next;
		}
		if(resA != null) {
			if(resB != null) {
				pA.next = resB;
				pB.next = null;
			} else {
				pA.next = null;
			}
			return resA;
		} else {
			pB.next = null;
			return resB;
		} 
		
//		if(head == null)
//			return null;
//		ListNode p = head;
//		ListNode endNode = head;
//		while(endNode.next != null) {
//			endNode = endNode.next;
//		}
//		if(head.val >= x) {
//			while(head.val >= x) {
//				endNode.next = head;
//				endNode = head;
//				head = head.next;
//				endNode.next = null;
//			}
//			p = head;
//		}
//		while(p.next != null) {
//			if(p.next.val >= x) {
//				endNode.next = p.next;
//				p.next = p.next.next;
//				endNode.next = endNode.next.next;
//				endNode.next = null;
//			}
//			p = p.next;
//		}
//		return head;
		
//		if(head == null)
//			return null;
//		ListNode p = head;
//		ListNode endNode = head;
//		while(endNode.next != null) {
//			endNode = endNode.next;
//		}
//		while(p.next != null) {
//			if(p.next.val == x) {
//				endNode.next = p.next;
//				endNode = p.next;
//				p.next = p.next.next;
//				endNode.next = null;
//			}
//			p = p.next;
//		}
//		if(head.val == x) {
//			endNode.next = head;
//			endNode = head;
//			head = head.next;
//			endNode.next = null;
//		}
//		while(head.val > x) {
//			endNode.next = head;
//			endNode = head;
//			head = head.next;
//			endNode.next = null;
//		}
//		p = head;
//		while(p.next != null) {
//			if(p.next.val > x) {
//				endNode.next = p.next;
//				endNode = p.next;
//				p.next = p.next.next;
//				endNode.next = null;
//			}
//			p = p.next;
//		}
//		return head;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
